class Solution:
    def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:
        # 判断s1是否可能包含s2
        for ch in s2:
            if ch not in s1:
                return 0

        i1, i2, j1 = 0, 0, 0

        # 依据循环节遍历
        count = {}
        while i1 < n1:
            # 循环一圈s2
            for j2 in range(len(s2)):
                while s1[j1] != s2[j2]:
                    j1 += 1
                    if j1 == len(s1):
                        i1 += 1
                        j1 = 0
                j1 += 1
                if j1 == len(s1):
                    i1 += 1
                    j1 = 0

            if i1 > n1 or (i1 == n1 and j1 > 0):
                break

            i2 += 1

            if j1 in count:  # 出现循环的情况
                ii1, ii2 = count[j1]
                # 直接循环到不足一个循环的情况
                times = (n1 - i1 - 1) // (i1 - ii1)
                # print(j1, 0, ":", ii1, ii2, ";", i1, i2, "->", times)
                i1 += times * (i1 - ii1)
                i2 += times * (i2 - ii2)
                break
            else:
                count[j1] = (i1, i2)

        # print("循环结束:", i1, i2, j1)

        # 遍历剩下的部分
        while i1 < n1:
            for j2 in range(len(s2)):
                while s1[j1] != s2[j2]:
                    j1 += 1
                    if j1 == len(s1):
                        i1 += 1
                        j1 = 0
                j1 += 1
                if j1 == len(s1):
                    i1 += 1
                    j1 = 0

            if i1 > n1 or (i1 == n1 and j1 > 0):
                break

            i2 += 1

        return i2 // n2


if __name__ == "__main__":
    # 2
    print(Solution().getMaxRepetitions(s1="acb", n1=4,
                                       s2="ab", n2=2))

    # 12
    print(Solution().getMaxRepetitions(s1="aaa", n1=20,
                                       s2="aaaaa", n2=1))

    # 4
    print(Solution().getMaxRepetitions(s1="aaa", n1=3,
                                       s2="aa", n2=1))

    # 2
    print(Solution().getMaxRepetitions(s1="bacaba", n1=3,
                                       s2="abacab", n2=1))

    # 0
    print(Solution().getMaxRepetitions(s1="musicforever", n1=10,
                                       s2="lovelive", n2=100000))
